1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| #include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
using namespace std;
struct T{
struct A{
int l, r, Min;
}a[maxn << 2];
void build(int cur, int l, int r){
a[cur].l = l, a[cur].r = r;
a[cur].Min = INF;
if (l == r) return;
int mid = l + r >> 1;
build(cur << 1, l, mid);
build(cur << 1 | 1, mid + 1, r);
}
void upd(int cur, int p, int k){
if (a[cur].l == a[cur].r){
a[cur].Min = min(a[cur].Min, k);
return;
}
int mid = a[cur].l + a[cur].r >> 1;
if (p <= mid) upd(cur << 1, p, k);
else upd(cur << 1 | 1, p, k);
a[cur].Min = min(a[cur << 1].Min, a[cur << 1 | 1].Min);
}
int Query(int cur, int l, int r){
if (a[cur].l > r || a[cur].r < l) return INF;
if (a[cur].l >= l && a[cur].r <= r) return a[cur].Min;
return min(Query(cur << 1, l, r), Query(cur << 1 | 1, l, r));
}
}t;
vector <int> v[maxn];
int n, Q, b[maxn], f[maxn], S = 0;
int main(){
scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", b + i), S += (1 - b[i]);
scanf("%d", &Q);
for (int l, r, i = 1; i <= Q; i++){
scanf("%d%d", &l, &r);
v[l].push_back(r);
} t.build(1, 1, n);
for (int i = 1; i <= n; i++) sort(v[i].begin(), v[i].end());
memset(f, 0x3f, sizeof f); f[0] = 0;
for (int i = 1; i <= n; i++){
for (int j = 0; j < v[i].size(); j++){
int r = v[i][j]; int tmp = min(f[i - 1], t.Query(1, max(1, i - 1), r));
if (tmp < f[r]) t.upd(1, r, f[r] = tmp);
}
f[i] = min(f[i], f[i - 1] + ((b[i] == 1) ? 1 : -1));
} printf("%d\n", S + f[n]);
return 0;
}
|